package com.yuhuan.data_structures;
/**
 *
 *数据结构
 * @author Guoyuhuan
 * @version 1.0
 */
class Fibnoacci{

    /**
     * 求第n+1项斐波那契数
     * @param n 第n+1项
     * @return sum 第n+1项的值
     */
    public static int fib(int n){
        return n<2 ? n : fib(n-1) + fib(n-2);
    }

    /**
     * 求第n项斐波那契数
     * @param n 第n项
     * @return sum 第n项的值
     */
    public static long fib2(int n){
        long sum = 0;
        long a = 0;
        long b = 1;
        for(int i = 1 ; i<=n ; i++){
            if(i<3){
                if(i == 1)
                    sum = a;
                else {
                    sum = b;
                }
            }
            else {
                sum = a + b;
                a = b;
                b = sum;
            }
        }
        return sum;
    }



    public static void main(String[] args) {
        System.out.println(fib2(22));
        System.out.println(fib(21));//由此可见，递归的斐波那契数列效率太低了，运算量太多了，复杂度成指数上升
    }
}

